package com.leetcode.LC;

import java.util.LinkedList;
import java.util.Queue;

public class LC53 {
    public int maxSubArray(int[] nums) {
        int maxValue = nums[0], sum;
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int num : nums) {
            queue.add(num);
            do {
                sum = 0;
                for (Integer integer : queue) {
                    sum += integer;
                }
                if (sum < num) {
                    queue.poll();
                }
            } while (sum < num);

            if (sum > maxValue) {
                maxValue = sum;
            }
        }
        return maxValue;
    }

    public int maxSubArray2(int[] nums) {
        int[] memo = new int[nums.length];
        memo[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            memo[i] = Math.max(nums[i] + memo[i - 1], nums[i]);
        }
        for (int i : memo) {
            System.out.print(i);
        }

        int max = nums[0];

        for (int i = 1; i < memo.length; i++) {
            max = Math.max(max, memo[i]);
        }

        return max;
    }

    public static void main(String[] args) {
        System.out.println(new LC53().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(new LC53().maxSubArray2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}
